/*
338. Counting Bits
Total Accepted: 4334 Total Submissions: 7838 Difficulty: Medium

Given a non negative integer number num. For every numbers i in the range 0 �� i �� num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

    It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
    Space complexity should be O(n).
    Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

    You should make use of what you have produced already.

Credits:
Special thanks to @ syedee for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
*/

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *countBits(int num, int *returnSize)
{
    int *ret = malloc((num + 1) * sizeof(int));
    int  i;
    *returnSize = (num + 1);
    ret[0] = 0;
    for(i = 1; i <= num; i++) {
        ret[i] = ret[i & (i - 1)] + 1;
    }
    return ret;
}

// count(n) = count(n >> 1) + (n & 1);
int *countBits(int num, int *returnSize)
{
    int *ret = malloc((num + 2) * sizeof(int));
    int  i;
    *returnSize = (num + 1);
    ret[0] = 0;
    ret[1] = 1;
    for(i = 2; i <= num; i += 2) {
        ret[i] = ret[i >> 1];
        ret[i + 1] = ret[i >> 1] + 1;
    }
    return ret;
}

// count(n) = count(n >> 1) + (n & 1);
int *countBits(int num, int *returnSize)
{
    int *ret = malloc((num + 4) * sizeof(int));
    int  i;
    *returnSize = (num + 1);
    ret[0] = 0;
    ret[1] = 1;
    ret[2] = 1;
    ret[3] = 2;
    for(i = 4; i <= num; i += 4) {
        int a = ret[i >> 1];
        ret[i] = a;
        ret[i + 1] = a + 1;
        ret[i + 2] = a + 1;
        ret[i + 3] = a + 2;
    }
    return ret;
}

class Solution
{
public:
    vector<int> countBits(int num)
    {
        vector<int> ret(num + 1, 0);
        int         i;
        for(i = 1; i <= num; i++) {
            ret[i] = ret[i & (i - 1)] + 1;
        }
        return ret;
    }
};